package com.leetcode;

/**
 * 330. 按要求补齐数组
 * 给定一个已排序的正整数数组 nums，和一个正整数n 。从[1, n]区间内选取任意个数字补充到nums中，
 * 使[1, n]区间内的任何数字都可以用num中某几个数字的和来表示。
 * 请输出满足上述要求的最少需要补充的数字个数。
 *输入: nums = [1,3], n = 6
 * 输出: 1
 * 解释:
 * 根据 nums里现有的组合[1], [3], [1,3]，可以得出1, 3, 4。
 * 现在如果我们将2添加到nums 中，组合变为: [1], [2], [3], [1,3], [2,3], [1,2,3]。
 * 其和可以表示数字1, 2, 3, 4, 5, 6，能够覆盖[1, 6]区间里所有的数。
 * 所以我们最少需要添加一个数字，且这个数为2。
 *
 * 方法：用[1,max]来表示1~max以内的任意整数，假设添加一个数k，则能表示的范围变为：
 *      [1,max]U[k,k]U[1+k,max+k] 化简-> [1,max]U[k,max+k]
 *      要想让区间连续，则 k <= max+1。比如：[1,5]U[7,10]，因为7>5+1，所以是没法构成[1,10]连续的
 *  所以，如果目前能表示的范围是[1,max]，当需要添加的时候，应添加 k = max + 1。才可以保证添加最少
 *  利用题目给出的数组的连续的
 */
public class MinPatches {
    public static void main(String[] args) {
        int[] nums = new int[]{1,3};
        // int n = 6;
        int cnt = minPatches(nums,Integer.MAX_VALUE);
        System.out.println("cnt = " + cnt);
    }
    public static int minPatches(int[] nums, int n) {
        if (nums.length == 0){
            return -1;
        }
        long max = 0;//最小的范围应该从[1,0]开始判断
        int cnt = 0;//计数
        for(int i = 0;i < nums.length;i++){
            int k = nums[i];
            if(k <= max + 1){
                max += k;
            } else{
                //添加的数为max+1
                long temp = max + 1;
                max += temp;
                System.out.print(temp + " ");
                cnt++;
                //i--表示当前的nums[i],需要再次被判断使用
                i--;
            }
            if(max >= n){
                break;
            }
        }
        while (max < n){
            long temp = max + 1;
            max += temp;
            System.out.print(temp + " ");
            cnt++;
        }
        return cnt;
    }
}
